/**
 *  @file nfa.c
 *  @brief Simulator for a non-deterministic finite automaton.
 *  @author Prashant Hebbar
 *  @date May 23, 1990.
 *  $Id: nfa.c 10 2007-06-28 20:08:57Z mfms $
 **/

/*
 *  Copyright (C) 1990, 1992, 2001  Matthias Stallmann, Prashant Hebbar.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include "Gdr.h"

#define MAX_TRANS 100	/* maximum number of simultaneous transitions */

#define EOLN '\n'
#define LAMBDA '^'

/* declarations and macros for the animation */
TWIN pwin;                      /* window for user prompts */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
                   hide_window(pwin))
#define SX 200		/* coordinates of window for string */
#define SY 20

/* transition(current_states,new_states,trans,ch): returns the new set
   of states after reading symbol ch (new_states is a result
   parameter); trans is another result parameter -- the list of
   transition edges used (these are highlighted in the function) */
void transition(int *current_states, int *new_states, edge *trans, char ch)
     /* bit vectors */
	             
	         
{
  vertex q;
  edge e;
  int j = 0;
  
  /* initialize new_states to be empty */
  for (q = 0; q < max_vertex(); q++)
    new_states[q] = FALSE;
  
  /* try out every possible transition */
  for (q = 0; q < max_vertex(); q++) 
    if (current_states[q] == TRUE) {
      for (e = first_out_edge(q); e != NULL_EDGE;
           e = next_out_edge(q,e)) {
		
        /* if ch occurs in the label of e then
           vertex at the other end of e is a new state */
        if (index(edge_label(e),ch)) {
          new_states[other_vertex(q,e)] = TRUE;
          if (j >= MAX_TRANS) {
            fprintf(stderr,"Too many transitions (nfa.c)");
            exit(1);
          }
          trans[j++] = e;
          highlight_edge(e);
        }
      }
    }
  trans[j] = NULL_EDGE;
}


/* dfs(i,new_states,trans): recursive depth-first search used to find
   lambda closure (new_states and trans are return parameters as in
   lambda_closure), j, the index into the trans array, is a
   reference parameter */
void dfs(int i, int *new_states, edge *trans, int *j)
{
  edge e;	/* current edge out of i */
  
  if (new_states[i]) return;	/* already visited */
  
  new_states[i] = TRUE;
  
  for (e = first_out_edge(i); e != NULL_EDGE;
       e = next_out_edge(i,e)) {
	
    /* if LAMBDA occurs in the label of e then
       vertex at the other end of e is a new state (and must be
       visited recursively) */
    if (index(edge_label(e),LAMBDA)) {
      if (*j >= MAX_TRANS) {
        fprintf(stderr,"Too many transitions (nfa.c)");
        exit(1);
      }
      trans[(*j)++] = e;
      highlight_edge(e);
	  
      dfs(other_vertex(i,e),new_states,trans,j);
    }
  }
}


/* lambda_closure(current_states,new_states): returns the set of states
   accessible from current_states via null transitions (new_states
   behaves as a result parameter); trans is another result parameter
   -- an array of transition edges used (these are highlighted in the
   function) */
void lambda_closure(int *current_states, int *new_states, edge *trans)
     /* bit vectors */
	             
{
  vertex i;
  int j=0;	/* index into trans */
  
  /* initialize new_states to be empty */
  for (i = 0; i < max_vertex(); i++)
    new_states[i] = FALSE;
  
  for (i = 0; i < max_vertex(); i++)
    if (current_states[i])
      dfs(i,new_states,trans,&j);
  
  trans[j] = NULL_EDGE;
}


/* do the NFA animation: assumes that vertex 0 is start
   state; input string is in label of vertex 0 */
void animat(void)
{
  int i;		/* used as index into vertex and edge vectors */
  int k;		/* used as index into input string */
  char stg[L_LAB],dstg[L_LAB+10]; /* input string for storage and
                                     display */
  TWIN swin;                    /* window to show string */
  int current_states[MAX_VERTEX], new_states[MAX_VERTEX];
  edge trans[MAX_TRANS+1]; /* set of transition edges */
  
  /* prompt user for input string */
  init_prompt_window;
  wait("Put input string in label\n of vertex 0 (the start state)\n and click Resume");
  
  /* read input string */
  strcpy(stg,vertex_label(0));
  hide_vertex_label(0);
  
  /* create window for string */
  sprintf(dstg,"> %s",stg);
  swin = create_text_window(SX,SY,dstg);
  
  /* initialize set of states */
  for (i = 0; i < max_vertex(); i++)
    current_states[i] = FALSE;
  current_states[0] = TRUE;
  
  /* compute lambda closure of the start state */
  lambda_closure(current_states,new_states,trans);
  for (i = 0; i < max_vertex(); i++)
    if (new_states[i]) highlight_vertex(i);
  
  /* compute new set of states as long as input remains (k is index of
     current character) 
     ****    MAIN LOOP    **** */
  for (k = 0; stg[k] != '\0'; k++) {
    /* update current states */
    for (i = 0; i < max_vertex(); i++)
      current_states[i] = new_states[i];
    wait("Next transition?\n (click Resume)");
    /* unhighlight edges from previous lambda closure */
    for (i = 0; trans[i] != NULL_EDGE; i++)
      un_highlight_edge(trans[i]);
	
    transition(current_states,new_states,trans,stg[k]);
	
    /* after a pause, unhighlight the current states
       and transition edges, and
       highlight the new states */
    wait("Show new states?\n (click Resume)");
    for (i = 0; i < max_vertex(); i++)
      if (current_states[i]) un_highlight_vertex(i);
    for (i = 0; trans[i] != NULL_EDGE; i++)
      un_highlight_edge(trans[i]);
    for (i = 0; i < max_vertex(); i++)
      if (new_states[i]) highlight_vertex(i);
	
    /* show remainder of string */
    sprintf(dstg,"> %s",&stg[k+1]);
    write_text_window(swin,dstg);
	
    /* update current states */
    for (i = 0; i < max_vertex(); i++)
      current_states[i] = new_states[i];
	
    /* compute lambda closure */
    lambda_closure(current_states,new_states,trans);
    for (i = 0; i < max_vertex(); i++)
      if (new_states[i]) highlight_vertex(i);
  }
  
  wait("Simulation done.\n (click resume to clean up)");
  for (i = 0; i < max_vertex(); i++)
    if (new_states[i]) un_highlight_vertex(i);
  for (i = 0; trans[i] != NULL_EDGE; i++)
    un_highlight_edge(trans[i]);
  destroy_prompt_window;
  kill_window(swin);
} /* animat ends */

/*  [Last modified: 2007 06 28 at 19:50:03 GMT] */
